1. Field of the Invention
This invention pertains to a system for solving an optimization problem, such as a traveling salesman (salesperson) problem. More specifically, it pertains to a problem solving operation apparatus, with a concept of state transition introduced, for expediting a search for an optimum solution.
2. Description of the Related Arts
A problem solving operation apparatus to which this invention pertains is an apparatus for obtaining the solution of a generic mathematical programming problem. Such mathematical programming problems include traffic control, the determination of an optimum transmission path for a packet especially in a communications network, power supply routing control for an electrical power network, a determination in dispatching freight in traffic system, transportation scheduling problems e.g. for trains, busses and airplanes, a load distribution system amongst parallelly operating processors, and the routing control of a coupling network among processors.
On solving a traveling salesman problem, which is a mathematical programming problem of finding a route for traveling N cities in the shortest distance without a second visit, an attempt made to utilize a conventional technique for obtaining an optimum solution by searching and evaluating all possible combinations, will exponentially increase the computing time as the number of the cities N increases. Such a problem is called NP hard (nondeterministic polynomial hard). It has already been known that an algorithm for obtaining an optimum solution within a polynomial timeframe does not exist.
From the standpoint of strictness, i.e. the degree of optimization of an obtained solution, conventional optimization techniques for such a mathematical programming problem can be categorized broadly into two schemes, A1 being a strict solution method for obtaining a strict optimum solution, and A2 being an approximate solution method for fast obtaining an approximate optimum solution.
As well, from the standpoint of methods for searching solutions, the conventional optimization techniques can be categorized into three schemes, B1 being a common listing method for obtaining a strict solution through a strict listing or an equivalent listing, B2 being a discovery method for heuristically reducing solution candidates into a single solution by using rules for generating an optimum solution or an approximately optimum solution, and B3 being a searching method for obtaining an approximately optimum solution through the search of a partial area in a solution space.
A genetic algorithm (GA), one of such optimization techniques, can be classified as a combination of A2 and B3 described above. It is based on a search for an optimum solution, after generating an initial group comprising a plurality of individuals having random genes, through a repetition of three types of genetic operations composed of a reproduction process, a crossover process and a mutation process, until a search terminating condition is satisfied.
Here, a reproduction process is defined as an operation for determining individuals of the current generation by randomly selecting a few of the individuals of a group belonging to the preceding generation. A crossover process is defined as an operation of partially swapping chromosome of two individuals for generating new individuals as offsprings. A mutation process is a process for swapping alleles or transmuting parts of chromosomes of an individual of a group to become a succeeding generation. A conventional genetic algorithm causes these three types of genetic operations to be repeated until a terminating condition for the search of an optimum solution (or optimum solutions) is satisfied.
Such a technique of searching an optimum solution by applying a genetic algorithm to a mathematical programming problem, however, has a disadvantage that the growth of a fitness value, defined as the value which increases when an objective value for the solution gets close to its optimum value, slows down, when the value of the generation reaches a large value, after a number of generations have passed. That is, there is a problem that as the value of the generation increases, the growth rate of the fitness value decreases.
When a problem has a substantial number of local optima or complexities, the consideration of this disadvantage poses particular importance, because it is difficult to search a solution giving a practically optimum fitness value within a realistic timeframe.